package demo.DataStrucAndAlgo.AlgorithmOfTen;

import java.util.*;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/9-08-09-22:48
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen     求最小生成树Mst   Kruskal算法（克鲁斯卡算法）
 */
/*
简称K算法：
    和prim算法一样都是求最小生成树，
    k算法算法分析：
        将各个边按权值大小排序，将排序的边按顺序选取，
        同时要满足所选取的边不能与之前选取的边形成回路。若不满足，就跳过该边。
    e.g.七个公交站点（A~G），需要将七个站点连通，每个路的长度（权）不同，如何修路使站点连通，且长度最短
        A~B 12  A~G 14  A~F 16
        B~C 10  B~F 7   C~F 6
        C~D 3   C~E 5   D~E 4
        E~G 8   E~F 2   G~F 9
 */
public class Kruskal {
    static HashSet<Character> vertexs = new HashSet<>(Arrays.asList('A','B','C','D','E','F','G'));
    public static void main(String[] args) {

        TreeMap<Integer, HashSet<Character>> map = new TreeMap();
        map.put(12,new HashSet(Arrays.asList('A','B')));
        map.put(14,new HashSet(Arrays.asList('A','G')));
        map.put(16,new HashSet(Arrays.asList('A','F')));
        map.put(10,new HashSet(Arrays.asList('B','C')));
        map.put(7,new HashSet(Arrays.asList('B','F')));
        map.put(6,new HashSet<>(Arrays.asList('C','F')));
        map.put(3,new HashSet(Arrays.asList('C','D')));
        map.put(5,new HashSet(Arrays.asList('C','E')));
        map.put(4,new HashSet(Arrays.asList('D','E')));
        map.put(8,new HashSet(Arrays.asList('E','G')));
        map.put(2,new HashSet(Arrays.asList('E','F')));
        map.put(9,new HashSet(Arrays.asList('G','F')));
        map.put(9,new HashSet(Arrays.asList('G','F')));
        System.out.println(map);
        HashSet<Integer> result = k_minTree(map);

        System.out.println("选取的边及权值为：");
        for (Integer key : result) {
            System.out.println(map.get(key) + "  ->  " + key);
        }
    }

    private static HashSet<Integer> k_minTree(TreeMap<Integer, HashSet<Character>> map) {

        HashSet<Integer> result = new HashSet<>();
        HashSet<Character> ver = new HashSet<>();
        for (Integer key : map.keySet()) {
            if(ver.containsAll(vertexs)){
                break;
            }
            HashSet<Character> vertex_two = map.get(key);
            if(ver.isEmpty() || !ver.containsAll(vertex_two)){
                ver.addAll(vertex_two);
                result.add(key);
            }
        }
        return result;
    }
}
